class Solution(object):
    def getMinDistSum(self, positions):
        delta = 10 ** (-10)
        learning_rate = 1
        decay = 10 ** (-3)
        n = len(positions)
        sum_x, sum_y = sum([item[0] for item in positions]), sum([item[1] for item in positions])
        x0 = sum_x / n
        y0 = sum_y / n
        last = 0
        for i in range(n):
            last += ((x0 - positions[i][0]) ** 2 + (y0 - positions[i][1]) ** 2) ** 0.5
        min_val = last
        diff = float('inf')
        while diff > delta:
            if last == 0:
                return 0
            delta_x = 0
            delta_y = 0
            for i in range(n):
                if ((x0 - positions[i][0]) ** 2 + (y0 - positions[i][1]) ** 2) ** 0.5 > 0:
                    delta_x += (positions[i][0] - x0) / ((x0 - positions[i][0]) ** 2 + (y0 - positions[i][1]) ** 2) ** 0.5
                    delta_y += (positions[i][1] - y0) / ((x0 - positions[i][0]) ** 2 + (y0 - positions[i][1]) ** 2) ** 0.5
            delta_x /= n
            delta_y /= n 
            x_diff = abs(delta_x * learning_rate)
            y_diff = abs(delta_y * learning_rate)
            x0, y0 = x0 + x_diff, y0 + delta_y * y_diff
            diff = max(abs(x_diff), abs(y_diff))
            now = 0
            for i in range(n):
                now += ((x0 - positions[i][0]) ** 2 + (y0 - positions[i][1]) ** 2) ** 0.5
            min_val = min(now, min_val)
            learning_rate *= (1 - decay)
        return min_val



data = Solution()
positions = [[0,1],[1,0],[1,2],[2,1]]
print(data.getMinDistSum(positions))
positions = [[1, 1], [3, 3]]
print(data.getMinDistSum(positions))
positions = [[1, 1], [0, 0], [2, 0]]
print(data.getMinDistSum(positions))
positions = [[27,90],[99,75],[99,38]]
print(data.getMinDistSum(positions))
positions = [[44,23],[18,45],[6,73],[0,76],[10,50],[30,7],[92,59],[44,59],[79,45],[69,37],[66,63],[10,78],[88,80],[44,87]]
print(data.getMinDistSum(positions))
positions = positions = [[55,91],[83,86],[48,8],[71,31],[50,28],[28,52],[89,18],[61,5],[100,100],[63,94],[93,49],[82,72],[17,9],[63,48],[83,96],[47,2],[43,50],[95,32],[87,74],[39,80],[57,15],[98,95],[37,53]]
print(data.getMinDistSum(positions))